package array;

/**
 * 53. 最大子数组和
 * <p>
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组是数组中的一个连续部分。
 * <p>
 * 示例 1：
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * <p>
 * 示例 2：
 * 输入：nums = [1]
 * 输出：1
 * <p>
 * 示例 3：
 * 输入：nums = [5,4,-1,7,8]
 * 输出：23
 */
public class Problem_53 {

    public static void main(String[] args) {
        System.out.println(new Problem_53().maxSubArray_1(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
        System.out.println(new Problem_53().maxSubArray_2(new int[]{5, 4, -1, 7, 8}));
    }

    /**
     * 贪心算法:
     * 在数学计算中，一个数x加上一个小于零的负数，其结果一定小于x。
     * 因此，对于当前位置来说，如果之前数据之和sum小于0，我们应当按照sum为0重新开始计算以求得最大和值。
     */
    public int maxSubArray_1(int[] nums) {
        int result = nums[0];
        int sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (sum < 0) {
                sum = 0;
            }
            sum += nums[i];
            result = Math.max(result, sum);
        }

        return result;
    }

    /**
     * 动态规划:
     * 在数学计算中，一个数x加上一个数y，y的数值越大，其和值就越大。
     * 也就是说，当前位置可取到的最大和值 = 当前位置处的数值x + 上一位置处可取到的最大和值y。
     */
    public int maxSubArray_2(int[] nums) {
        int result = nums[0];
        int temp = nums[0];
        for (int i = 1; i < nums.length; i++) {
            temp = Math.max(nums[i], temp + nums[i]);
            result = Math.max(result, temp);

        }
        return result;
    }

}
